import java.util.*;
/**
 * 
 * 括号生成
 * 
 * 描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：
0
≤
n
≤
10
0≤n≤10
要求：空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
2
n
)
O(2 
n
 )

 */
public class 括号生成 {
    
    public static void main(String[] args) {
        
        generateParenthesis(3).stream().forEach(System.out::println);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public static ArrayList<String> generateParenthesis (int n) {
        // write code here

        ArrayList<String> result = new ArrayList<>();
        String curr = "";
        generate(result, curr, 0, 0, n);
        return result;
    }

    private static void generate(ArrayList<String> result, String curr, int open, int close, int n) {
        if (curr.length() == 2 * n) {
            result.add(curr);
            return;
        }
        if (open < n) {
            generate(result, curr+"(", open + 1, close, n);
        }
        if (close < open) {
            generate(result, curr+")", open, close + 1, n);
        }
    }
}
